public  class KRotateRightArray{

	public static void KsortArray(int input[],int d)
	{
		int n = input.length;
		int start = 0; 
		int end = n-d-1;
		
		for(int i = 0; i < n; i++)
		System.out.print(input[i]+" ");

		input = reverse(input,start,end);
		start = n-d;
		end = n-1;
		

		System.out.println();
		for(int i = 0; i < n; i++)
		System.out.print(input[i]+" ");

		
		input = reverse(input,start,end);
		start = 0; 
		end = n-1;
		

		System.out.println();
		for(int i = 0; i < n; i++)
		System.out.print(input[i]+" ");

		input = reverse(input,start,end);

		System.out.println();
		for(int i = 0; i < n; i++)
		System.out.print(input[i]+" ");

	}

	public static void main(String[] args) {
		int input[] = {1,2,3,4,5};

		KsortArray(input,2);
		System.out.println();
		System.out.println(search(input,2));
	}

	private static  int[] reverse(int[] input,int start, int end)
	{
		while(start < end)
		{
			int temp = input[start];
			input[start] = input[end];
			input[end] = temp;
			start+=1;
			end-=1;

		}
		return input;
	}

	private static int search(int[] input, int key)
	{
		int start = 0;
		int end = input.length-1;
		int mid = start + (end-start)/2;

		while(start < end)
		{
		if(input[mid]==key) return mid;
		
		if(input[mid]>input[start])
		{
			if(input[mid]>key)
			{
				end = mid-1;
			}

			else
			{
				start = mid+1;
			}
		}

		else
		{
			if(input[mid]>key)
			{
				start = mid + 1;
			}

			else
			{
				end = mid-1;
			}	
		}

		mid = start + (end-start)/2;
	}
	return -1;
	}
}